package Hard;

import java.util.Stack;

//25.K个一组翻转链表
public class Solution25 {
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) return head;
        ListNode p = head;
        ListNode preP = null;
        while (p != null) {
            ListNode q = p;

            for (int i = 1; i < k && q != null; i++) {
                q = q.next;
            }

            if (q == null) {
                // 这部分不用翻转
                preP.next = p;
                break;
            }

            ListNode t = q.next;
            reverse(p, q);
            if (preP != null) {
                preP.next = q;
            } else {
                head = q;
            }
            preP = p;
            p = t;
        }
        return head;
    }

    public static void reverse(ListNode start, ListNode end) {
        ListNode pre = null;
        ListNode p = start;
        ListNode post = p.next;
        while (p != end) {
            p.next = pre;
            pre = p;
            p = post;
            if (p != null) {
                post = p.next;
            }
        }

    }

    public static ListNode reverseKGroup2(ListNode head, int k) {
        if (k == 1) return head;
        ListNode p = head;
        boolean first = true;
        Stack<ListNode> stack = new Stack<>();
        ListNode pre = null;
        while (p != null) {

            for (int i = 0; i < k && p != null; i++) {
                stack.push(p);
                p = p.next;
            }
            if (stack.size() < k)
                //如果栈不满，则结束循环
                break;
            while (!stack.empty()) {
                ListNode a = stack.peek();
                if (first) {
                    first = false;
                    head = a;
                }
                stack.pop();
                if (stack.size() == k - 1) {
                    //修正
                    if (pre != null)
                        pre.next = a;
                }
                try {
                    a.next = stack.peek();
                } catch (Exception e) {
                    //a.next应该等于后面子链表排序好以后的第一个元素
                    a.next = p;
                    pre = a; //下一次循环的时候通过pre修正a.next的真正应该指向的地方
                }

            }
        }
        return head;
    }

    public static void main(String[] args) {
        reverseKGroup(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))), 2);
    }

}
